class Solution:
    def nextGreaterElement(self, n: int) -> int:
        '''
        1 5 8 4 7 6 5 3 1
        从右向左找到第一个降序的数
        1 5 8 4 7 6 5 3 1
              。
        然后从最右向左找到第一个比 a 大的数 b
        1 5 8 4 7 6 5 3 1
              。    。
        交换这两个数 [num[a], num[b]] = [num[b], num[a]]
        1 5 8 5 7 6 4 3 1  
              。    。
        将 a 右边的数全部反转
        1 5 8 5 1 3 4 6 7
              。    
        done!
        '''
        s = str(n)
        max = s[-1]
        a, b = -1, -1
        # 从右向左找到第一个比后一数小的数 a
        for i in range(len(s)-2, -1, -1):
            if s[i] < max:
                a = i
                break
            max = s[i]
        
        if a == -1:
            return -1
        
        # 然后从最右向左找到第一个比 a 大的数 b
        for i in range(len(s)-1, a, -1):
            if s[i] > s[a]:
                b = i
                break
        
        # 交换这两个数 [num[a], num[b]] = [num[b], num[a]]
        s = s[:a] + s[b] + s[a+1:b] + s[a] + s[b+1:]
        # 把a后边的数按小到大排序
        ans = s[0:a+1] + s[a+1:][::-1]
        try:
            return int(ans) if int(ans) <= 2**31-1 else -1
        except:
            return -1

        
        